home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 1.iso / toolbox / documents / Inventor / www / workarounds / PickingFixes.2.0.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-11-11  |  10.0 KB  |  334 lines
  1. //
  2. // This is a patch for Inventor 2.0's picking routines, which are
  3. // extremely slow when doing world-space picking.
  4. //
  5. // To apply this patch, compile this file into a .o and then link
  6. // the .o before -lInventor.
  7. // The linker may give a warning about
  8. // multiply defined symbols. This is normal and expected.
  9. //
  10.  
  11. #include <Inventor/SbLinear.h>
  12. #include <Inventor/SbBox.h>
  13.  
  14. ////////////////////////////////////////////////////////////////////////
  15. //
  16. // Description:
  17. //    Intersects view volume with box. Returns TRUE if intersection.
  18. //
  19. // Use: internal
  20.  
  21. SbBool
  22. SbViewVolume::intersect(const SbBox3f &box) const
  23. //
  24. ////////////////////////////////////////////////////////////////////////
  25. {
  26.     // Empty bboxes can cause problems:
  27.     if (box.isEmpty()) return FALSE;
  28.  
  29.     //
  30.     // The bounding box is the set of all points between its bounds;
  31.     // that is, all points (x,y,z) such that:
  32.     //        x_min <= x <= x_max
  33.     //        y_min <= y <= y_max
  34.     //        z_min <= z <= z_max
  35.     // (Inventor bounding boxes are axis-aligned)
  36.     //
  37.     // We will consider there to be no intersection if all of those
  38.     // points are on the 'outside' side of any of the view-volume
  39.     // planes (this may pass some things that could be culled, but
  40.     // will never cull things that are visible). So we want to see if
  41.     // any point is on the inside, in which case the intersection
  42.     // returns TRUE.
  43.     //
  44.     // The equation of the view-volume planes is Ax+By+Cz=D, where
  45.     // (A,B,C) is the plane normal and D is the distance from the
  46.     // origin. The condition for a point (x,y,z) being on the
  47.     // 'outside' side is Ax+By+Cz-D < 0. We need to test the largest
  48.     // value of Ax+By+Cz-D to see if it is negative. If it is, then we
  49.     // know all points are outside.
  50.     //
  51.     // We can minimize the number of point/plane checks we do by
  52.     // noticing that Ax+By+Cx-D will be greatest when each of its
  53.     // terms is greatest; for example, if A is positive, Ax will be
  54.     // greatest when x is x_max. If A is negative, Ax will be greatest
  55.     // when x is x_min.
  56.     // So, we can reduce the test to a check of one point against each
  57.     // of the 6 plane equations. The outsideTest() method does this.
  58.     //
  59.  
  60.     SbVec3f min, max;
  61.     box.getBounds(min, max);
  62.  
  63.     // OPPORTUNITY FOR OPTIMIZATION HERE:  We could precompute planes
  64.     // and save some work.
  65.  
  66.     if (type == PERSPECTIVE) {
  67.     // Left plane is formed from eye, llf, ulf
  68.     SbPlane leftPlane(projPoint, llf, ulf);
  69.     if (outsideTest(leftPlane, min, max))
  70.         return FALSE;
  71.  
  72.     // Figure out urf point:
  73.     SbVec3f urf = lrf + (ulf - llf);
  74.     // Right is eye, urf, lrf
  75.     SbPlane rightPlane(projPoint, urf, lrf);
  76.     if (outsideTest(rightPlane, min, max))
  77.         return FALSE;
  78.  
  79.     // Near is lrf, llf, ulf:
  80.     SbPlane nearPlane(lrf, llf, ulf);
  81.     if (outsideTest(nearPlane, min, max))
  82.         return FALSE;
  83.  
  84.     // Far is near points in opposite order, translated to far plane:
  85.     SbVec3f farOffset = nearToFar * projDir;
  86.     SbPlane farPlane(ulf+farOffset, llf+farOffset, lrf+farOffset);
  87.     if (outsideTest(farPlane, min, max))
  88.         return FALSE;
  89.  
  90.     // Bottom is eye, lrf, llf
  91.     SbPlane bottomPlane(projPoint, lrf, llf);
  92.     if (outsideTest(bottomPlane, min, max))
  93.         return FALSE;
  94.  
  95.     // Finally, top is eye, ulf, urf
  96.     SbPlane topPlane(projPoint, ulf, urf);
  97.     if (outsideTest(topPlane, min, max))
  98.         return FALSE;
  99.     }
  100.  
  101.     else {            // type == ORTHOGRAPHIC
  102.     // Left plane is formed from llf, lff+projDir, ulf
  103.     SbPlane leftPlane(llf, llf+projDir, ulf);
  104.     if (outsideTest(leftPlane, min, max))
  105.         return FALSE;
  106.  
  107.     // Figure out urf point:
  108.     SbVec3f urf = lrf + (ulf - llf);
  109.     // Right is urf+projDir, lrf, urf
  110.     SbPlane rightPlane(urf+projDir, lrf, urf);
  111.     if (outsideTest(rightPlane, min, max))
  112.         return FALSE;
  113.  
  114.     // Near is lrf, llf, ulf:
  115.     SbPlane nearPlane(lrf, llf, ulf);
  116.     if (outsideTest(nearPlane, min, max))
  117.         return FALSE;
  118.  
  119.     // Far is near points in opposite order, translated to far plane:
  120.     SbVec3f farOffset = nearToFar * projDir;
  121.     SbPlane farPlane(ulf+farOffset, llf+farOffset, lrf+farOffset);
  122.     if (outsideTest(farPlane, min, max))
  123.         return FALSE;
  124.  
  125.     // Bottom is lrf, lrf+projDir, lrf, llf
  126.     SbPlane bottomPlane(lrf, lrf+projDir, llf);
  127.     if (outsideTest(bottomPlane, min, max))
  128.         return FALSE;
  129.  
  130.     // Finally, top is urf, ulf, ulf+projDir
  131.     SbPlane topPlane(urf, ulf, ulf+projDir);
  132.     if (outsideTest(topPlane, min, max))
  133.         return FALSE;
  134.     }
  135.  
  136.     return TRUE;
  137. }
  138.  
  139. #include <Inventor/actions/SoRayPickAction.h>
  140.  
  141. ////////////////////////////////////////////////////////////////////////
  142. //
  143. // Description:
  144. //    Intersects object-space bounding box with current ray. Returns
  145. //    success or failure.
  146. //
  147. // Use: extender
  148.  
  149. SbBool
  150. SoRayPickAction::intersect(const SbBox3f &box)
  151. //
  152. ////////////////////////////////////////////////////////////////////////
  153. {
  154.     // If the ray was set as a world-space line, we don't really have
  155.     // a valid object-space view volume to test against the box. (The
  156.     // view volume is a degenerate case - a line.) So just use the
  157.     // object-space line to do the intersection.
  158.     if (lineWasSet) {
  159.     SbVec3f enter, exit;
  160.     return objLine.intersect(box, enter, exit);
  161.     }
  162.  
  163.     else
  164.     return objVol.intersect(box);
  165. }
  166.  
  167. ////////////////////////////////////////////////////////////////////////
  168. //
  169. // Description:
  170. //    Intersects the line with the triangle formed bu v0, v1, v2.
  171. //    Returns TRUE if there is an intersection. If there is an
  172. //    intersection, barycentric will contain the barycentric
  173. //    coordinates of the intersection (for v0, v1, v2, respectively)
  174. //    and front will be set to TRUE if the ray intersected the front
  175. //    of the triangle (as defined by the right hand rule).
  176. //
  177. // Use: internal
  178.  
  179. SbBool
  180. SbLine::intersect(const SbVec3f &v0, const SbVec3f &v1, const SbVec3f &v2,
  181.           SbVec3f &intersection,
  182.           SbVec3f &barycentric, SbBool &front) const
  183. //
  184. ////////////////////////////////////////////////////////////////////////
  185. {
  186.     //////////////////////////////////////////////////////////////////
  187.     //
  188.     // The method used here is described by Didier Badouel in Graphics
  189.     // Gems (I), pages 390 - 393.
  190.     //
  191.     //////////////////////////////////////////////////////////////////
  192.  
  193. #define EPSILON    1e-10
  194.  
  195.     //
  196.     // (1) Compute the plane containing the triangle
  197.     //
  198.     SbVec3f    v01 = v1 - v0;
  199.     SbVec3f    v12 = v2 - v1;
  200.     SbVec3f    norm = v12.cross(v01);    // Un-normalized normal
  201.     // Normalize normal to unit length, and make sure the length is
  202.     // not 0 (indicating a zero-area triangle)
  203.     if (norm.normalize() < EPSILON)
  204.     return FALSE;
  205.  
  206.     //
  207.     // (2) Compute the distance t to the plane along the line
  208.     //
  209.     float d = getDirection().dot(norm);
  210.     if (d < EPSILON && d > -EPSILON)
  211.     return FALSE;            // Line is parallel to plane
  212.     float t = norm.dot(v0 - getPosition()) / d;
  213.     if (t <= 0.0)            // Ignore intersections behind eye
  214.     return FALSE;
  215.  
  216.     //
  217.     // (3) Find the largest component of the plane normal. The other
  218.     //     two dimensions are the axes of the aligned plane we will
  219.     //     use to project the triangle.
  220.     //
  221.     float    xAbs = norm[0] < 0.0 ? -norm[0] : norm[0];
  222.     float    yAbs = norm[1] < 0.0 ? -norm[1] : norm[1];
  223.     float    zAbs = norm[2] < 0.0 ? -norm[2] : norm[2];
  224.     int        axis0, axis1;
  225.  
  226.     if (xAbs > yAbs && xAbs > zAbs) {
  227.     axis0 = 1;
  228.     axis1 = 2;
  229.     }
  230.     else if (yAbs > zAbs) {
  231.     axis0 = 2;
  232.     axis1 = 0;
  233.     }
  234.     else {
  235.     axis0 = 0;
  236.     axis1 = 1;
  237.     }
  238.  
  239.     //
  240.     // (4) Determine if the projected intersection (of the line and
  241.     //     the triangle's plane) lies within the projected triangle.
  242.     //     Since we deal with only 2 components, we can avoid the
  243.     //     third computation.
  244.     //
  245.     float intersection0 = getPosition()[axis0] + t * getDirection()[axis0];
  246.     float intersection1 = getPosition()[axis1] + t * getDirection()[axis1];
  247.  
  248.     SbVec2f    diff0, diff1, diff2;
  249.     SbBool    isInter = FALSE;
  250.     float    alpha, beta;
  251.  
  252.     diff0[0] = intersection0 - v0[axis0];
  253.     diff0[1] = intersection1 - v0[axis1];
  254.     diff1[0] = v1[axis0]     - v0[axis0];
  255.     diff1[1] = v1[axis1]     - v0[axis1];
  256.     diff2[0] = v2[axis0]     - v0[axis0];
  257.     diff2[1] = v2[axis1]     - v0[axis1];
  258.  
  259.     isInter = FALSE;
  260.     if (diff1[0] < EPSILON && diff1[0] > -EPSILON) {
  261.     beta = diff0[0] / diff2[0];
  262.     if (beta >= 0.0 && beta <= 1.0) {
  263.         alpha = (diff0[1] - beta * diff2[1]) / diff1[1];
  264.         isInter = (alpha >= 0.0 && alpha + beta <= 1.0);
  265.     }
  266.     }
  267.     else {
  268.     beta = ((diff0[1] * diff1[0] - diff0[0] * diff1[1]) /
  269.         (diff2[1] * diff1[0] - diff2[0] * diff1[1]));
  270.     if (beta >= 0.0 && beta <= 1.0) {
  271.         alpha = (diff0[0] - beta * diff2[0]) / diff1[0];
  272.         isInter = (alpha >= 0.0 && alpha + beta <= 1.0);
  273.     }
  274.     }
  275.  
  276.     //
  277.     // (5) If there is an intersection, set up the barycentric
  278.     //     coordinates and figure out if the front was hit.
  279.     //
  280.     if (isInter) {
  281.     barycentric.setValue(1.0 - (alpha + beta), alpha, beta);
  282.     front = (getDirection().dot(norm) < 0.0);
  283.     intersection = getPosition() + t * getDirection();
  284.     }
  285.  
  286.     return isInter;
  287.  
  288. #undef EPSILON
  289. }
  290.  
  291. #include <Inventor/actions/SoPickAction.h>
  292.  
  293. ////////////////////////////////////////////////////////////////////////
  294. //
  295. // Description:
  296. //    Constructor.
  297. //
  298. // Use: protected
  299.  
  300. SoPickAction::SoPickAction(const SbViewportRegion &viewportRegion)
  301. //
  302. ////////////////////////////////////////////////////////////////////////
  303. {
  304.     SO_ACTION_CONSTRUCTOR(SoPickAction);
  305.     vpRegion = viewportRegion;
  306.  
  307.     enableCulling(TRUE);
  308. }
  309.  
  310. #include <Inventor/SoPickedPoint.h>
  311. #include <Inventor/elements/SoModelMatrixElement.h>
  312.  
  313. ////////////////////////////////////////////////////////////////////////
  314. //
  315. // Description:
  316. //    Sets the object-space normal.
  317. //
  318. // Use: extender
  319.  
  320. void
  321. SoPickedPoint::setObjectNormal(const SbVec3f &normal)
  322. //
  323. ////////////////////////////////////////////////////////////////////////
  324. {
  325.     // Transform the object space normal by the current modeling
  326.     // matrix o get the world space normal. Use the inverse transpose
  327.     // of the odel matrix so that normals are not scaled incorrectly.
  328.     SbMatrix normalMatrix =
  329.     SoModelMatrixElement::get(state).inverse().transpose();
  330.  
  331.     normalMatrix.multDirMatrix(normal, worldNormal);
  332.     worldNormal.normalize();
  333. }
  334.